#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    bool backtrace(vector<string>& ret, unordered_map<string, map<string, int>>& targets, int& num)
    {
        if (ret.size() == num)
            return true;
        /*for(auto& it:targets)
        {
            cout<<it.first<<" "<<ret[ret.size() - 1]<<endl;
            if(it.first==ret[ret.size() - 1])
            {
                for(auto& e: it.second)
                {
                    if (e.second > 0)
                    {
                        ret.push_back(e.first);
                        e.second--;
                        if (backtrace(ret, targets, num))
                            return true;
                        ret.pop_back();
                        e.second++;
                    }
                }
            }
        }*/
        for (auto& e : targets[ret[ret.size() - 1]])
        {
            if (e.second > 0)
            {
                ret.push_back(e.first);
                e.second--;
                if (backtrace(ret, targets, num))
                    return true;
                ret.pop_back();
                e.second++;
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> ret;
        unordered_map<string, map<string, int>> targets;
        targets.clear();
        for (auto& e : tickets)
            targets[e[0]][e[1]]++;
        ret.push_back("JFK");
        int num = tickets.size() + 1;
        backtrace(ret, targets, num);
        return ret;
    }
};

class Solution {
public:
    void _generateParenthesisR(vector<string>& ret, string& s, int left, int right, int& n)
    {
        if (left == n && right == n)
        {
            ret.push_back(s);
            return;
        }
        else if (left < right)
        {
            return;
        }
        else if (left == n && right < n)
        {
            s += ')';
            _generateParenthesisR(ret, s, left, right + 1, n);
            s.pop_back();
            return;
        }
        s += '(';
        _generateParenthesisR(ret, s, left + 1, right, n);
        s.pop_back();
        s += ')';
        _generateParenthesisR(ret, s, left, right + 1, n);
        s.pop_back();
    }

    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        string s;
        _generateParenthesisR(ret, s, 0, 0, n);
        return ret;
    }
};